class Node {
    constructor(value, next = null) {
        this.value = value
        this.left = null
        this.right = null
    }
}

// 用数组储存二叉搜索树
class bstree{
    constructor() {
        this.root = null
    }
    /**
     * 添加, 如果相等，添加到右树
     */
    add(item, tree = this.root){
        if (!tree){ //空树
            this.root = new Node(item)
            return;
        }
        if (!(tree.left || tree.right)){ // 再没有子节点了，开始进入比较的正题
            if (item >= tree.value){
                tree.right = new Node(item)
            }else {
                tree.left = new Node(item)
            }
            return
        }
        // 看来还是有子节点呀
        //   从根节点开始遍历，如果比根节点小，继续往左走，否则，往右走
        if (item >= tree.value){
            // 大于等于去右树
            this.add(item,tree.right)
        }else {
            // 小于，去左子树
            this.add(item, tree.left)
        }
    }
    // 查找元素
    find(item, tree = this.root){
        if (!tree){
            return null
        }
        if (tree.value == item){
            return tree;
        }else if (item<tree.value){
            return this.find(item, tree.left)
        }else {
            return this.find(item, tree.right)
        }
    }
    // 删除操作
    // 叶子结点直接删除
    // 有一个子节点直接摞到他的位置就行。。。子节点后面的都要摞
    // 有两个子节点，需要把右节点的最小叶子节点摞上来，或者左节点的最大叶子节点，其他不变
    del(item){
        this.root = this.removeNode(item, this.root)
        return this.root
    }
    removeNode(item, tree){
        if (tree.value === item){
            if (!(tree.left || tree.right)){ // 左右节点都没有 叶子节点
                return null // 返回null 相当于把自己删除了
            }else if (tree.left !==null && tree.right !== null) { // 左右节点都有
                let tree = tree.right
                // 右子树最小值
                while (tree.left !== null){
                    tree = tree.left
                }
                return tree
            }else if (tree.left) { // 只有一个左节点，
                return tree.left
            }else {
                return tree.right
            }
        }else if (item < tree.value){
            tree.left = this.removeNode(item, tree.left)
        }else {
            tree.right = this.removeNode(item, tree.right)
        }
        return tree
    }
    // tree sort
    // 先序遍历
    preOrder(tree = this.root){
        if (tree){
            console.log(tree.value)
            this.preOrder(tree.left)
            this.preOrder(tree.right)
        }
    }
    // 中序遍历
    midPrint(tree = this.root){
        if (!tree){
            return;
        }
        if (!(tree.left || tree.right)){ // 到叶子节点了，打印下自己就退出
            console.log(tree.value)
            return
        }
        // 看来还没到叶子节点
        // 先左边
        this.midPrint(tree.left)
        console.log(tree.value)
        this.midPrint(tree.right)
    }
}

let bt = new bstree()
bt.add(1)
bt.add(2)
bt.add(55)
bt.add(3)
bt.midPrint()

console.log("查找",JSON.stringify(bt.find(2)))
console.log("删除",JSON.stringify(bt.del(2)))

